package com.Questions.tanxin;



/*
 1.贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。
 也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
 2.贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
 这是贪心算法可行的第一个基本要素。
 3.当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
 运用贪心策略在每一次转化时都取得了最优解。
 问题的最优子结构性质是该问题可用贪心算法求解的关键特征。
 贪心算法的每一次操作都对结果产生直接影响。
 贪心算法对每个子问题的解决方案都做出选择，不能回退。
 4.贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，
 每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。
 若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，
 直到把所有数据枚举完，或者不能再添加算法停止。
 5.实际上，贪心算法适用的情贪心算法(贪婪算法)况很少。
 一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，
 就可以做出判断。

 如果这个贪心策略不能找到所有的分割 那么必然存在一个分割 它的左右两边则LR数量不相同
 这和平衡字符串的定义不相同 所以所有的分割必然被找到

该算法存在的问题
1.不能保证求得的最后解是最佳的
2.不能用来求最大值或最小值的问题
3.只能求满足某些约束条件的可行解的范围


 */

/**
 * 分割平衡字符串
 */
public class leetcode1221 {
    public int balancedStringSplit(String s) {
        // 解题思路 不要有嵌套的平衡 只要有平衡 就立即分割
        // R=-1 L=1 只要累加为0就立即分割 贪心策略
            int cnt = 0;
            int balance = 0;
            for(int i = 0; i < s.length(); i++){
                if(s.charAt(i) == 'L')
                    balance--;
                if(s.charAt(i) == 'R')
                    balance++;
                if(balance == 0)
                    cnt++;
            }
            return cnt;
    }
}
